package com.lwl.leetcode.滑动窗口;

import java.util.LinkedList;

/**
 * @author lwl
 * @Description TODO
 * @date 2025/9/1 16:32
 */
public class Code1856MaxSumMinProduct {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 2};
        System.out.println(maxSumMinProduct(nums));
    }

    // [1,2,3,4, 5]
    //  0 1 2 3  4
    //  1 3 6 10 15
    public static int maxSumMinProduct(int[] nums) {
        int MOD = 1000000007;
        // 前缀和
        long[] sums = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sums[i + 1] = nums[i] + sums[i];
        }
        // 从左往右单调递增栈
        LinkedList<Integer> queue = new LinkedList<>();
        long res = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!queue.isEmpty() && nums[i] <= nums[queue.peekLast()]) {
                Integer curLast = queue.pollLast();
                int l = queue.isEmpty() ? 0 : queue.peekLast() + 1;
                int r = i;
                res = Math.max(res, (long) nums[curLast] * (sums[r] - sums[l]));
            }
            queue.addLast(i);
        }
        while (!queue.isEmpty()) {
            Integer curLast = queue.pollLast();
            int l = queue.isEmpty() ? 0 : queue.peekLast() + 1;
            int r = nums.length;
            res = Math.max(res, (long) nums[curLast] * (sums[r] - sums[l]));
        }
        return (int) (res % MOD);
    }
}
